package Hash;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

public class groupAnagrams {
    // 使用暴力的方式，sort char[]当作key
    public static List<List<String>> groupAnagrams(String[] strs) {
        HashMap<List<Character>, List<String>> map = new HashMap<>();
        for (String str : strs) {
            // 转换成字符list
            ArrayList<Character> arrayList = new ArrayList<>();
            for (char c : str.toCharArray()) {
                arrayList.add(c);
            }
            // 排序
            Collections.sort(arrayList);
            List<String> subList = map.get(arrayList);
            if (subList == null || subList.size() == 0) {
                subList = new ArrayList<>();
            }
            subList.add(str);
            map.put(arrayList, subList);
        }
        List<List<String>> list = new ArrayList<>();
        for (List<Character> key : map.keySet()) {
            list.add(map.get(key));
        }
        return list;
    }

    // 因为每个str中，每个字符出现的次数一样，因此将26个字母出现的顺序作为key
    public static List<List<String>> groupAnagrams2(String[] strs) {
        HashMap<String,List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            // 定义长度为26的数组记录字母出现的频率（因为只有小写）
            int[] count = new int[26];
            for(char c : strs[i].toCharArray()){
                //对应位+1
                count[c-'a']++;
            }
            //tostring生成的不一样
            //需要手动拼接
            //拼接存在问题，可能出现["bdddddddddd","bbbbbbbbbbc"]导致结果相同的问题
            //因此得用字符拼，而不是次数拼
            String key = "";
            
            for(int j =0;j<count.length;j++){
                key+=(count[j]+'a');
            }
        
            List<String> list = map.getOrDefault(key,new ArrayList<>());
            list.add(strs[i]);
            map.put(key, list);
        }
        List<List<String>> result = new ArrayList<>();
        for(List<String> li : map.values()){
            result.add(li);
        }
        return result;

    }

    public static void main(String[] args) {
        // String[] strs = new String[] { "eat", "tea", "tan", "ate", "nat", "bat" };
        // String[] strs = new String[] { "a" };
        String[] strs = new String[] { "bdddddddddd","bbbbbbbbbbc" };
        List<List<String>> groupAnagrams = groupAnagrams2(strs);
        for (List<String> list : groupAnagrams) {
            System.out.println("===============");
            for (String string : list) {
                System.out.println(string);
            }
        }
    }
}
